package twobranchTree.levelorder;

import java.util.ArrayList;
import java.util.List;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/2/20
 * @author 王光浩
 * @Description 给定一颗二叉树，使用层序遍历该树。
 * @Thinking 使用递归的方法。
 */
public class MyMethodTwo {
    public List<List<Integer>> levelOrder(TreeNode root) {
    	List<List<Integer>> result=new ArrayList<List<Integer>>();
    	if(root!=null)level(root,1,result);
    	return result;
    }
    private void level(TreeNode node,int level,List<List<Integer>> result) {
    	if(result.size()>=level)result.get(level-1).add(node.val); //该层已被创建
    	else {   //该层没有被创建
    		ArrayList<Integer> tem=new ArrayList<Integer>();
    		tem.add(node.val);
    		result.add(tem);
    	}
    	if(node.left!=null)level(node.left,level+1,result);
    	if(node.right!=null)level(node.right,level+1,result);
    }
    
    private List<List<Integer>> ret;
    public List<List<Integer>> levelOrder1(TreeNode root) {
    	ret = new ArrayList<List<Integer>>();
    	helper(root, 1);
    	return ret;
    }
    private void helper(TreeNode node, int level) {
    	if (node == null)
    		return;
    	if (level > ret.size())
    		ret.add(new ArrayList<Integer>());
    	ret.get(level-1).add(node.val);
    	helper(node.left, level + 1);
    	helper(node.right, level + 1);
    }
}
